The goal of the Cgal Open Source Project is to provide easy access to efficient and reliable geometric algorithms in the form of a C++ library.
The Computational Geometry Algorithms Library offers data structures and algorithms like triangulations, Voronoi diagrams, Boolean operations on polygons and on polyhedra, arrangements of curves, mesh generation, geometry processing, convex hull algorithms, to name just a few.
All these data structures and algorithms operate on geometric objects like points and segments, and perform geometric tests on them. These objects and predicates are regrouped in Cgal Kernels.
Finally, the Cgal Support Library offers geometric object generators and spatial sorting functions, as well as a matrix search framework and a solver for linear and quadratic programs. It further offers interfaces to third party software such as the Gui libraries Qt, Geomview, and the Boost Graph Library.
This manual is organized in several parts covering the many domains of computational geometry. Each part consists of several chapters, and each chapter is split into a user manual and a reference manual. The user manual gives the general idea and comes with examples. The reference manual presents the Api of the various classes and functions.
The manual has a table of contents, and an index, as well as a package overview, which gives a short paragraph what the package is about, what license it has, and on which other packages it depends. It further provides links to precompiled demo programs for the Windows platform.
In the distribution of the library you find the two directories demo and examples. They contain subdirectories for the Cgal packages. The demos use third party libraries for the graphical user interface. The examples don't have this dependency and most examples are refered to in the user manual.
In this section we will take a closer look at three Cgal example programs, all of them computing the 2D convex hull of a set of points.
In the first example we have an array of five points. As the convex hull of these points is a subset of the input it is safe to provide an array for storing the result which has the same size.
File: examples/Convex_hull_2/array_convex_hull_2.cpp
#include <iostream>
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/convex_hull_2.h>
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_2 Point_2;
int main()
{
Point_2 points[5] = { Point_2(0,0), Point_2(10,0), Point_2(10,10), Point_2(6,5), Point_2(4,1) };
Point_2 result[5];
Point_2 *ptr = CGAL::convex_hull_2( points, points+5, result );
std::cout << ptr - result << " points on the convex hull" << std::endl;
return 0;
}
All Cgal header files are in the subdirectory ``include/CGAL''. All Cgal classes and functions are in the namespace ``CGAL''. The geometric primitives, like the point type, are defined in a kernel. Cgal comes with several kernels, and as the convex hull algorithm only makes comparisons of coordinates and orientation tests of input points, we can choose a kernel that provides exact predicates, but no exact geometric construction.
The convex hull function takes three arguments, the start and past-the-end pointer for the input, and the start pointer of the array for the result. The function returns the pointer into the result array just behind the last convex hull point written, so the pointer difference tells us how many points are on the convex hull.
In the second example we replace the built-in array by a std::vector of the Standard Template Library.
File: examples/Convex_hull_2/vector_convex_hull_2.cpp
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/convex_hull_2.h>
#include <vector>
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_2 Point_2;
typedef std::vector<Point_2> Points;
int main()
{
Points points, result;
points.push_back(Point_2(0,0));
points.push_back(Point_2(10,0));
points.push_back(Point_2(10,10));
points.push_back(Point_2(6,5));
points.push_back(Point_2(4,1));
CGAL::convex_hull_2( points.begin(), points.end(), std::back_inserter(result) );
std::cout << result.size() << " points on the convex hull" << std::endl;
return 0;
}
We put some points in the vector calling the push_back() method of the std::vector class.
We then call the convex hull function. The first two arguments, points.begin() and points.end() are iterators, which are a generalization of pointers: they can be dereferenced and incremented. The convex hull function is generic in the sense that it takes as input whatever can be dereferenced and incremented.
The third argument is where the result gets written to. In the previous example we provided a pointer to allocated memory. The generalization of such a pointer is the output iterator, which allows to increment and assign a value to the dereferenced iterator. In this example we start with an empty vector which grows as needed. Therefore, we cannot simply pass it result.begin(), but an output iterator generated by the helper function std::back_inserter(result). This output iterator does nothing when incremented, and calls result.push_back(..) on the assignment.
The last example program reads a sequence of points from standard input std::cin and writes the points on the convex hull to standard output std::cout.
Instead of storing the points in a container such as an std::vector, and passing the begin/end iterator of the vector to the convex hull function, we use helper classes that turn file pointers into iterators.
File: examples/Convex_hull_2/iostream_convex_hull_2.cpp
#include <iostream>
#include <iterator>
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/convex_hull_2.h>
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_2 Point_2;
int main()
{
std::istream_iterator< Point_2 > input_begin( std::cin );
std::istream_iterator< Point_2 > input_end;
std::ostream_iterator< Point_2 > output( std::cout, "\n" );
CGAL::convex_hull_2( input_begin, input_end, output );
return 0;
}
In the example code you see input and output stream iterators templated with the point type. A std::istream_iterator<Point_2> hence allows to traverse a sequence of objects of type Point_2, which come from standard input as we pass std::cin to the constructor of the iterator. The variable input_end denotes end-of-file.
A std::ostream_iterator<Point_2> is an output iterator, that is an iterator to which, when dereferenced, we can assign a value. When such an assignment to the output iterator happens somewhere inside the convex hull function, the iterator just writes the assigned point to standard output, because the iterator was constructed with std::cout.
The call to the convex hull function takes three arguments, the input iterator range, and the output iterator to which the result gets written.
If you know the STL, the Standard Template Library, the above makes perfect sense, as this is the way the STL decouples algorithms from containers. If you don't know the STL, you maybe better first familiarize yourself with its basic ideas.
Additional documents accompanying the Cgal distribution are the `Installation Guide'. We also recommend the standard text books by Josuttis [Jos99], or Austern [Aus98] for the STL and its notion of concepts and models.
Other resources for Cgal are the tutorials at http://www.cgal.org/Tutorials/ and the user support page at http://www.cgal.org/.